#include <iostream>
#include <vector>

using namespace std;
class Solution 
{
public:
    int minTrace(vector<vector<int>>& triangle)
    {
        int m = triangle.size();
        vector<vector<int>> dp(m, vector<int>(m, 0));
        dp[0][0] = triangle[0][0];

        for (int i = 1; i < m; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (j == 0)
                {
                    dp[i][j] = dp[i - 1][j] + triangle[i][j];
                }
                else if (j == i)
                {
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                }
                else 
                {
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
                }
            }
        }

        int res = INT_MAX;
        for (int i = 0; i < m; i++)
        {
            res = min(res, dp[m - 1][i]);
        }

        return res;
    }
};

int main()
{
    vector<vector<int>> v{ {2},{3, 4},{6, 5, 7},{4, 1, 8, 3} };
    Solution xz;
    int n = xz.minTrace(v);
    cout << n << endl;

	return 0;
}